package 数组;

import java.util.Arrays;

/**
 * 力扣：27
 *
 * @Author zxl
 * @Date 2022/1/1 20:48
 * @Desc 原地移除数组中所有等于val的元素，要求不能使用额外的辅助空间，即空间复杂度O(1)，返回移除元素后新数组的size
 */
public class 移除元素 {

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 4, 4, 4};
        int[] nums2 = {0, 1, 2, 3, 3, 0, 4};
        int val = 4;
//        System.out.println("nums:" + Arrays.toString(nums) + ",移除: " + val + "后的size：" + removeVal2(nums, val));
//        System.out.println("移除后的数组：" + Arrays.toString(nums));
//        System.out.println("nums2:" + Arrays.toString(nums2) + ",移除: " + val + "后的size：" + removeVal2(nums2, val));
//        System.out.println("移除后的数组：" + Arrays.toString(nums2));
        removeVal3(nums, 4);
    }


    public static void removeVal3(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                // 覆盖
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        System.out.println(nums);
    }


    /**
     * 双指针
     * 时间复杂度O(n)
     * 快慢指针一起出发，遇到目标元素后，快指针继续走，慢指针不走
     * 快指针指向的值覆盖慢指针指向的值，达到数组元素前移的效果
     *
     * @param nums 123445
     * @param val
     * @return
     */
    public static int removeVal2(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                // 覆盖
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }

    /**
     * 双循环暴力破解
     * 时间复杂度O(n^2)
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeVal(int[] nums, int val) {
        int size = nums.length;
        // 临界条件为size，如果是nums.length的话，当目标元素在数组尾部，会导致死循环（比如：4, 5, 6, 4, 4, 4）
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                // 后面的元素全部往前移动一位
                for (int j = i + 1; j < nums.length; j++) {
                    nums[j - 1] = nums[j];
                }
                size--;
                i--;
            }
        }
        return size;
    }

    /**
     * 快慢指针
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeVal4(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                // 覆盖慢指针
                nums[slowIndex] = nums[fastIndex];
                // 满指针前进
                slowIndex++;
            }
        }
        return slowIndex;
    }

    /**
     * 删除有序数组中的重复项
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度
     * @param nums
     * @return 2223445
     */
    public static int deleteRepeat(int[] nums){
        int slowIndex = 1;
        for (int fastIndex = 1;fastIndex<nums.length;fastIndex++){
            if (nums[fastIndex] != nums[fastIndex -1]){
                nums[slowIndex] = nums[fastIndex];
                slowIndex ++;
            }
        }
        return slowIndex;

    }
}
